//: [Previous](@previous)

import Foundation
import GeekTime_PageSources

var greeting = "Hello, playground"

//: [Next](@next)


// 链表反转
let testList = NodeList()
                        .appendToTail(1)
                        .appendToTail(2)
                        .appendToTail(3)
                        .appendToTail(4)
                        .appendToTail(5)
func reverseList(_ list: NodeList) -> NodeList {
    // 当前节点
    var currentNode = list.head
    // 前一个节点
    var previousNode: Node?
    // 后一个节点
    var nextNode: Node?
    
    while currentNode != nil {
        // 暂时保存下一个节点
        nextNode = currentNode?.next
        // 反转当前节点的指针
        currentNode?.next = previousNode
        
        // 将当前节点作为 previous 节点
        previousNode = currentNode
        // 继续处理下一个节点
        currentNode = nextNode
    }
    list.head = previousNode
    return list

}
reverseList(testList)


// 无序数组中的中位数

// 冒泡/快速/堆排


class SortsPractice {
    
    class func bubbleSort(array: inout [Int]) {
        var times = 0
        // 1. 遍历每一个元素去和其他元素做比对
        for i in 0..<array.count {
            // 2. 从第一轮遍历的元素后开始遍历
            for j in i+1..<array.count {
                if array[j] < array[i] {
                    array.swapAt(i, j)
                }
                times += 1
            }
        }
        print(times)
        print(array)
    }
    
    /*
     1.确定基线条件
     2.递归
        1. 取出第一个元素pivot, 创建less, more数组
        2. 遍历后续元组, current<pivot, 加入less中, 否则加入more中
        3. 递归合并, less + [pivot] + more
     */
    class func quickSort(arr: inout [Int]) -> [Int] {
        // 基线条件
        if arr.count < 2 {
            return arr
        } else {
            // 递归
            let pivot = arr.first!
            var less = [Int]()
            var more = [Int]()
            for i in 1..<arr.count {
                let current = arr[i]
                if current < pivot {
                    less.append(current)
                } else {
                    more.append(current)
                }
            }
            return quickSort(arr: &less) + [pivot] + quickSort(arr: &more)
        }
    }
    
}
var sortArray = [1,5,2,6,3,9]
//SortsPractice.bubbleSort(array: &sortArray)
SortsPractice.quickSort(arr: &sortArray)

// MARK: - LRU算法
class LRUCache<Key: Hashable, Value> {
    private class CacheNode {
        let key: Key
        var value: Value
        var next: CacheNode?
        weak var prev: CacheNode?
        
        init(key: Key, value: Value) {
            self.key = key
            self.value = value
        }
    }
    
    private var capacity: Int
    private var cache: [Key: CacheNode]
    private var head: CacheNode?        //最早使用的节点
    private var tail: CacheNode?        //最新使用的节点
    
    init(capacity: Int) {
        self.capacity = capacity
        self.cache = [:]
    }
    
    // 获取缓存中的值
    func get(_ key: Key) -> Value? {
        guard let node = cache[key] else { return nil }
        moveToTail(node)
        return node.value
    }
    
    // 更新插入新缓存值
    func put(_ key: Key, _ value: Value) {
        if let node = cache[key] {
            node.value = value
            moveToTail(node)
        } else {
            // 插入新值
            let newNode = CacheNode(key: key, value: value)
            if cache.count >= capacity {
                removeHead()
            }
            addToTail(newNode)
            cache[key] = newNode
        }
    }
    
    
    private func moveToTail(_ node: CacheNode) {
        removeNode(node)
        addToTail(node)
    }
    
    private func addToTail(_ node: CacheNode) {
        if let tailNode = tail {
            tailNode.next = node
            node.prev = tailNode
        }
        
        tail = node
        
        if head == nil {
            head = node
        }
    }
    
    // 移除最早使用的节点
    private func removeHead() {
        guard let headNode = head else { return }
        cache[headNode.key] = nil
        head = headNode.next
        if head == nil {
            tail = nil
        }
    }
    
    // 移除节点
    private func removeNode(_ node: CacheNode) {
        if let preNode = node.prev {
            preNode.next = node.next
        } else {
            head = node.next
        }
        
        if let nextNode = node.next {
            nextNode.prev = node.prev
        } else {
            tail = node.prev
        }
    }
}



class Solution {
    static func decodeString(_ s: String) -> String {
        var result = ""
        var sectionCount = 0
        var sectionString = ""
        for c in s {
            // 数字
            if let value = c.wholeNumberValue {
                // 记录字数
                sectionCount = value
                sectionString = ""
            } else if c == "[" { // 开始
                continue
            } else if c == "]" { // 结束
                result.append(String(repeating: sectionString, count: sectionCount))
                // 清空分区信息
                sectionCount = 0
                sectionString = ""
            } else {
                // 积累字符
                sectionString += String(c)
            }
        }
        return result
    }
    
    static func decodeString2(_ s: String) -> String {
        var stack: [(Int, String)] = []  // 用栈来存储数字和当前的字符串
        var currentString = ""  // 当前正在处理的字符串
        var currentNumber = 0  // 当前数字，用于表示重复次数
        for char in s {
            if let digit = char.wholeNumberValue {
                // 如果是数字，更新当前的数字
                currentNumber = currentNumber * 10 + digit
            } else if char == "[" {
                // 遇到左括号，表示新的一层开始
                stack.append((currentNumber, currentString))
                currentString = ""  // 清空当前字符串，准备接收新的部分
                currentNumber = 0  // 重置数字
            } else if char == "]" {
                // 遇到右括号，表示一层结束
                if let (repeatCount, previousString) = stack.popLast() {
                    // 将解码后的字符串重复相应次数
                    currentString = previousString + String(repeating: currentString, count: repeatCount)
                }
            } else {
                // 普通字符，直接拼接到当前字符串
                currentString.append(char)
            }
        }
        
        return currentString
    }
}

Solution.decodeString2("3[a2[c]]")

//let s = "3[a]2[bc]"
//Solution.decodeString(s)


